package com.xjl.sort;

/**
 * @描述： 小和问题
 * @作者： 许JIAN林
 */
public class Test01 {

    public static int  CountSmallSum(int[] arr) {
        int count = 0;
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    count += arr[j];
                }
            }
        }
        return count;

    }
    public static int mergesort(int[] arr, int L, int R) {

        if (arr == null || arr.length<=2){
            return 0 ;
        }
        if (L == R) {
            return 0 ;
        }

        // int mid = (L + R) / 2;
        int mid = L + ((R - L) >> 1);
        return mergesort(arr, L, mid) + mergesort(arr, mid + 1, R) + merge(arr, L, mid, R);

    }

    public static int merge(int[] arr, int L, int mid, int R) {

        int[] help = new int[R - L + 1];
        int i = 0;
        int res = 0;
        int p1 = L;
        int p2 = mid+1;

        while (p1 <= mid && p2 <= R){
            res += arr[p1] < arr[p2]? (R - p2 + 1) * arr[p1] : 0;
            help[i++] = arr[p1] < arr[p2]? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while ( p2 <= R) {
            help[i++] = arr[p2++];
        }

        for (int j =0; j<help.length; j++) {
            arr[L+j] = help[j];
        }

        return res;

    }



    public static void main(String[] args) {
        int[] arr = {1,3,4,2,5};
        int sum = CountSmallSum(arr);
        int mergesort = mergesort(arr, 0, arr.length - 1 );
        System.out.println("简单实现"+sum);
        System.out.println("使用分治思想"+mergesort);
    }


}
